# 作者: 家里蹲 吴越洋
# 2023年02月28日20时06分21秒

import queue

class Node(object):
    # 结点
    def __init__(self,data=-1,lchild=None,rchild=None):
        self.data=data
        self.lchild=lchild
        self.rchild=rchild

class Tree(object):
    def __init__(self):
        self.root=None
        self.queue=[]
    #层次建树
    def build_tree(self,data):
        new_node=Node(data)
        if self.root is None:
            self.root=new_node
            self.queue.append(new_node)
            return
        if self.queue[0].lchild is None:
            self.queue[0].lchild=new_node
            self.queue.append(new_node)
        else:
            self.queue[0].rchild=new_node
            self.queue.append(new_node)
            self.queue.pop(0)

    #先序遍历，即深度优先遍历
    def pre_order(self,node):
        if node != None:
            print(node.data,end=' ')
            self.pre_order(node.lchild)
            self.pre_order(node.rchild)

    #中序遍历
    def mid_order(self,node):
        if node is None:
            return
        self.mid_order(node.lchild)
        print(node.data,end=' ')
        self.mid_order(node.rchild)

    #后序遍历
    def post_order(self,node):
        if node != None:
            self.post_order(node.lchild)
            self.post_order(node.rchild)
            print(node.data, end=' ')

    #层序遍历
    def level_order(self,node):
        self.queue.clear()
        self.queue.append(node)
        while len(self.queue)!=0:
            if self.queue[0].lchild != None:
                self.queue.append(self.queue[0].lchild)
            if self.queue[0].rchild != None:
                self.queue.append(self.queue[0].rchild)
            print(self.queue[0].data,end=' ')
            self.queue.pop(0)


if __name__ == '__main__':
    tree=Tree()
    for i in range(10):
        tree.build_tree(i)
    tree.pre_order(tree.root)
    print('\n')
    tree.mid_order(tree.root)
    print('\n')
    tree.post_order(tree.root)
    print('\n')
    tree.level_order(tree.root)